import org.junit.Test;

public class LeetCode {
    @Test 
    public void test1(){
        int n=12;
        System.out.println(numSquares(n));
    }


    public int numSquares(int n) {
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            int iSqrt=(int)Math.sqrt(i);
            int temp=dp[i-iSqrt*iSqrt];
            for(int j=1;j<iSqrt;j++){
                temp=Math.min(temp, dp[i-j*j]);
            }
            dp[i]=1+temp;
        }
        return dp[n];
    }


}
